package leetcode.D2000.T1514;

import java.util.*;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-19 18:09:42 星期六
 */

class Solution {

    static class Node {
        int dst;
        double prob;

        public Node(int dst, double prob) {
            this.dst = dst;
            this.prob = prob;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<Node>[] graph = buildGraph(n, edges, succProb);
        return dijstra(graph, start, end);
    }

    private List<Node>[] buildGraph(int n, int[][] edges, double[] succProb) {
        List<Node>[] graph = new List[n];
        for (int i=0; i<n; ++i)
            graph[i] = new ArrayList<>();
        for (int i=0; i<succProb.length; ++i) {
            int a = edges[i][0], b = edges[i][1];
            double prob = succProb[i];
            graph[a].add(new Node(b, prob));
            graph[b].add(new Node(a, prob));
        }
        return graph;
    }

    private double dijstra(List<Node>[] graph, int start, int end) {
        double[] dist = new double[graph.length];
        Set<Integer> vset = new HashSet<>();
        Set<Integer> tempSet = new HashSet<>();
        dist[start] = 1.0;
        tempSet.add(start);
        for (int i=0; i<graph.length; ++i) {
            int t = -1;
            double maxDist = 0;
            Iterator<Integer> it = tempSet.iterator();
            while (it.hasNext()) {
                int j = it.next();
                if (dist[j] > maxDist) {
                    t = j;
                    maxDist = dist[j];
                }
            }
            if (t < 0)
                break;
            vset.add(t);
            tempSet.remove(t);
            for (Node node : graph[t]) {
                if (!vset.contains(node.dst)) {
                    dist[node.dst] = Math.max(dist[node.dst], node.prob*dist[t]);
                    tempSet.add(node.dst);
                }
            }
        }
        return dist[end];
    }
}